sbox = [[0 for col in range(0x10)] for row in range(0x10)]
inv_sbox = [[0 for col in range(0x10)] for row in range(0x10)]
def degree(value):
    if value == 0:
        raise Exception("Value must be positive")
    degree = -1
    while value > 0:
        degree += 1
        value >>= 1
    return degree


def divide(dividend, divisor):
    if dividend < divisor:
        return 0, dividend
    d1 = degree(dividend)
    d2 = degree(divisor)

    diff = d1 - d2
    dividend ^= divisor << diff

    quotient, remainder = divide(dividend, divisor)
    quotient ^= 1 << diff

    return quotient, remainder


def multiply(mul1, mul2):
    if mul1 == 0 or mul2 == 0:
        return 0
    product = 0
    while mul2 > 0:
        d2 = degree(mul2)
        mul2 ^= 1 << d2
        product ^= mul1 << d2
    return product


def inverse(value):
    # algorithm see README
    if value == 0 or value == 1:
        return value
    mod = 0x11B
    dividend = mod
    divisor = value
    auxiliary1 = 0x0
    auxiliary2 = 0x1
    while divisor != 1:
        quotient, remainder = divide(dividend, divisor)
        dividend = divisor
        divisor = remainder
        temp = multiply(auxiliary2, quotient) ^ auxiliary1
        auxiliary1 = auxiliary2
        auxiliary2 = temp
        # print("divisor = 0x%02x, quotient = 0x%02x, auxiliary = 0x%02x" % (divisor, quotient, auxiliary2))
    return auxiliary2


# print("degree of 0x11b is %d" %(degree(0x11b)))
# print("degree of 0x1 is %d" %(degree(1)))

dividend = 0x11b
divisor = 0x11
# quotient, remainder = divide(dividend, divisor);
# print("%02x / %02x: quotient = %02x, remainder = %02x" % (dividend, divisor, quotient, remainder))
# divisor = 0x10
# quotient, remainder = divide(dividend, divisor);
# print("%02x / %02x: quotient = %02x, remainder = %02x" % (dividend, divisor, quotient, remainder))
# divisor = 0x01
# quotient, remainder = divide(dividend, divisor);
# print("%02x / %02x: quotient = %02x, remainder = %02x" % (dividend, divisor, quotient, remainder))

mul1 = 0xd
mul2 = 0x1
# product = multiply(mul1, mul2)
# print("0x%02x * 0x%02x: product = 0x%02x" % (mul1, mul2, product))

value = 0x10
# inverse_value = inverse(value)
# print("inverse(0x%02x) = 0x%02x" % (value, inverse_value))

def initialize():
    for i in range(0x10):
        for j in range(0x10):
            value = (i << 4) + j
            temp = inverse(value)
            sbox[i][j] = temp

def map(value):
    result = 0x0
    c = 0x63
    for i in range(8):
        temp = ((value >> i) & 0x1)
        temp ^= ((value >> ((i + 4) % 8)) & 0x1)
        temp ^= ((value >> ((i + 5) % 8)) & 0x1)
        temp ^= ((value >> ((i + 6) % 8)) & 0x1)
        temp ^= ((value >> ((i + 7) % 8)) & 0x1)
        temp ^= ((c >> i) & 0x1)
        result |= (temp << i)
    return result



def calculate_sbox():
    for i in range(0x10):
        for j in range(0x10):
            sbox[i][j] = map(sbox[i][j])


def inverse_sbox():
    for i in range(0x10):
        for j in range(0x10):
            value = sbox[i][j]
            row = value >> 4
            col = value & 0xF
            inv_sbox[row][col] = (i << 4) + j


def print_sbox(sbox):
    for i in range(0x10):
        for j in range(0x10):
            print("%02x" % (sbox[i][j]), end=' ')
        print("")

print("Initialize sbox:")
initialize()
print_sbox(sbox)
print("Calculate sbox:")
calculate_sbox()
print_sbox(sbox)
print("Inverse sbox:")
inverse_sbox()
print_sbox(inv_sbox)

